package com.klun.project.common.constans.leetcode;

// 给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。
// 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
// 示例 1:
// 输入: head = [-10,-3,0,5,9]
// 输出: [0,-3,9,-10,null,5]
// 解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
// 示例 2:
// 输入: head = []
// 输出: []
// 提示:
// head 中的节点数在[0, 2 * 104] 范围内
// -105 <= Node.val <= 105
// Related Topics 树 二叉搜索树 链表 分治 二叉树


import com.klun.project.common.constans.entity.ListNode;
import com.klun.project.common.constans.entity.TreeNode;
import com.klun.project.common.constans.utils.ParseUtils;

public class Solution109 {
	ListNode globalHead;

	public TreeNode sortedListToBST(ListNode head) {
		globalHead = head;
		int len = getLength(head);
		return buildTree(0, len - 1);
	}

	public int getLength(ListNode head) {
		int ret = 0;
		while (head != null) {
			++ret;
			head = head.next;
		}
		return ret;
	}

	public TreeNode buildTree(int left, int right) {
		if (left > right) {
			return null;
		}
		int mid = (left + right + 1) / 2;
		TreeNode tn = new TreeNode();
		tn.left = buildTree(left, mid - 1);
		tn.val = globalHead.val;
		globalHead = globalHead.next;
		tn.right = buildTree(mid + 1, right);
		return tn;
	}

	public static void main(String[] args) {
		Solution109 solution = new Solution109();
		ListNode treeNode = ParseUtils.ArrayToListNode("[-10,-3,-2,0,3,5,7,9]");
		TreeNode treeNode1 = solution.sortedListToBST(treeNode);
		System.out.println(treeNode);
		System.out.println(treeNode1);
	}

}
